package LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class LC_403_FrogJump {

    public static void main(String[] args) {

    }

    public class Solution {
        public boolean canCross(int[] stones) {
            int len = stones.length;
            Map<Integer, HashSet<Integer>> map = new HashMap<>();
            for (int stone : stones) map.put(stone, new HashSet<>());
            map.get(0).add(1);
            for (int i = 0; i < len - 1; i ++) {
                for (int step : map.get(stones[i])) {
                    int to = step + stones[i];
                    if (to == stones[len - 1]) return true;
                    HashSet<Integer> tmp = map.get(to);
                    if (tmp != null) {
                        tmp.add(step);
                        if (step > 1) tmp.add(step - 1);
                        tmp.add(step + 1);
                    }
                }
            }
            return false;
        }

    }
}
